📚 数据库系统导论：查询优化器 (Query Optimizer) 自学讲义#

1. 核心概念解释#

• 查询优化器的定位：它是数据库系统的“大脑”。应用程序发送 SQL 查询，优化器负责将其转化为系统可执行的高效物理执行计划 (Physical Plan)。
• 处理流程：
  1. Parser (解析器)：将 SQL 文本解析为抽象语法树 (AST)。
  2. Binder (绑定器)：查阅系统目录 (Catalog)，将 AST 中的字符串（表名、列名）映射为内部对象 ID，生成逻辑计划 (Logical Plan)。
  3. Optimizer (优化器)：输入逻辑计划，利用转换规则 (Transformation Rules) 和成本模型 (Cost Model)，生成最优的物理计划 (Physical Plan)。
• 逻辑计划 vs. 物理计划：
  • 逻辑计划：描述“做什么” (What)，例如“连接表 A 和 B”。
  • 物理计划：描述“怎么做” (How)，例如“使用 Hash Join 算法连接表 A 和 B”。

2. 关键结论 / 方法#

• 目标：生成的计划必须与原查询语义等价 (Equivalent)，即保证结果正确的前提下寻找成本最低的计划。
• 复杂性：连接顺序的选择是 NP-Hard 问题。随着表数量增加，搜索空间呈指数级增长。
• 单查询优化：绝大多数系统一次只优化一个查询，不考虑多查询间的资源竞争或共享。

3. 易混点或易错点提示#

• ⚠️ Binder 与 Optimizer 的区别：Binder 只是做名称解析和语义检查（表是否存在），不涉及算法选择；Optimizer 才决定用哪个索引或 Join 算法。
• ⚠️ 物理计划不唯一：一个逻辑操作符（如 Join）可能对应多种物理操作符（Hash Join, Sort Merge Join, Nested Loop Join），且可能不是一对一映射。

4. 简短复习小结#

查询优化器是连接 SQL 语句与执行引擎的桥梁。它通过解析、绑定、优化三个阶段，将声明式的 SQL 转化为具体的物理执行路径。理解逻辑计划与物理计划的区别是学习后续内容的基础。

1. 核心概念解释#

• 启发式/规则优化 (Rule-based)：基于关系代数的等价性，通过静态规则重写查询计划。这种方法通常不需要计算成本（Cost），因为这些转换通常总是“有益的”。
• 关系代数等价性：例如，选择操作 (Selection) 和连接操作 (Join) 通常满足交换律和结合律，允许调整操作顺序而不改变结果。

2. 关键结论 / 公式 / 方法#

• 常见转换规则：
  • 谓词下推 (Predicate Pushdown)：将过滤条件尽可能提前执行（下推到树的底部），以减少后续操作的数据量。
  • 投影下推 (Projection Pushdown)：尽早丢弃不需要的列，减少 I/O 和内存开销。
  • 分解联合谓词：将 WHERE A=1 AND B=2 拆分为两个独立的过滤算子，以便灵活移动。
  • 消除笛卡尔积：除非强制要求，否则总是将笛卡尔积 (Cross Join) 转换为内连接 (Inner Join)。

3. 易混点或易错点提示#

• ⚠️ 交换律的例外：虽然大多数 Join 满足交换律，但外连接 (Outer Join) 不满足（受 NULL 值处理影响），不能随意交换顺序。
• ⚠️ 局限性：纯启发式规则无法解决复杂问题（如：做 Hash Join 还是 Sort Merge Join 更好？A Join B 还是 B Join A？），这需要依赖数据分布的统计信息和成本模型。

4. 简短复习小结#

启发式规则是优化的第一步，核心思想是“尽早过滤数据” (Filter Early)。通过谓词下推、列裁剪等无需成本估算的重写规则，可以显著缩减后续搜索空间，是所有现代优化器的标配。

1. 核心概念解释#

• 搜索策略：在通过规则生成大量候选计划后，如何遍历这些计划并找到最优解。主要分为自底向上 (Bottom-up) 和自顶向下 (Top-down)。
• 计划枚举 (Enumeration)：生成不同连接顺序（Join Order）和物理实现（Physical Operator）的过程。

2. 关键结论 / 公式 / 方法#

• 自底向上 (Bottom-up) - System R 风格：
  • 方法：使用动态规划 (Dynamic Programming)。先计算所有基表的最佳访问路径，再计算两表连接的最佳路径，逐步向上扩展直到覆盖所有表。
  • 剪枝策略：System R 仅考虑左深树 (Left-deep trees)，即右侧操作数必须是基表，不考虑 bushy trees，以减少搜索空间。
• 自顶向下 (Top-down) - Volcano/Cascades 风格：
  • 方法：从目标结果开始，递归地通过转换规则将其分解为子目标。使用记忆化 (Memoization) 技术缓存已计算过的子树成本，避免重复计算。
  • 优势：更易于实现按需搜索和复杂的剪枝（Branch-and-bound），被 SQL Server 等现代系统广泛采用。

3. 易混点或易错点提示#

• ⚠️ System R 的假设：虽然 Bottom-up 效率高，但 System R 原始实现忽略了数据的物理属性（如排序顺序），这可能导致错失某些利用现有顺序的更优计划（如 Merge Join 需要排序输入）。现代实现会改进这一点。
• ⚠️ 超时机制：为了防止搜索时间过长，优化器通常有限制。SQL Server 甚至通过限制“应用规则的次数”而非“挂钟时间”来确保同一查询在不同负载下的计划一致性。

4. 简短复习小结#

搜索算法解决了“如何在指数级搜索空间中找到好计划”的问题。自底向上（动态规划）是经典做法，适合结构化搜索；自顶向下（Cascades）更灵活，支持按需展开和物理属性传递，是现代高端系统的首选。

1. 核心概念解释#

• 成本模型 (Cost Model)：用于估算计划执行代价的内部度量标准，通常基于 I/O 次数、CPU 开销等，并不直接等于实际运行时间。
• 统计信息 (Statistics)：存储在 Catalog 中的关于表数据的元数据，如直方图、不同值数量 (Distinct Values) 等。
• 基数估计 (Cardinality Estimation)：预测每个操作符输出的行数，这是成本计算的基础。

2. 关键结论 / 公式 / 方法#

• 统计数据结构：
  • 直方图 (Histograms)：最常用。等宽直方图 (Equi-width) 桶宽相同；等深直方图 (Equi-depth) 桶内元组数量相同（更能适应倾斜数据）。
  • Sketches：概率数据结构（如 HyperLogLog），用于估算去重计数等。
  • 采样 (Sampling)：对表进行随机采样来估算，SQL Server 甚至在优化时实时采样。
• 三大假设 (用于简化估算)：
  1. 均匀分布 (Uniformity)：假设值在桶内或表中均匀分布。
  2. 独立性 (Independence)：假设谓词之间相互独立（P(A and B) = P(A) * P(B)）。
  3. 包含原则 (Containment)：连接估算时，假设内表的键总是存在于外表中。
• 估算公式示例：
  • Selectivity = (Val - Low) / (High - Low) (针对范围查询)。
  • Join Size = (Size(R) * Size(S)) / max(Domain(key)) (简化版)。

3. 易混点或易错点提示#

• ⚠️ 相关性灾难：如果列之间强相关（如“车型=雅阁”与“品牌=本田”），独立性假设会导致严重的低估 (Underestimation)。可以通过多列统计信息 (Correlated Statistics) 缓解。
• ⚠️ 误差传播：底层的基数估算误差会随着 Join 层级向上传播，导致上层估算偏离几个数量级，最终选错 Join 算法（例如该用 Hash Join 却选了 Nested Loop）。
• ⚠️ 统计信息滞后：统计信息不是实时更新的，通常依赖后台任务或手动 ANALYZE。过期的统计信息会导致糟糕的计划。

4. 简短复习小结#

成本模型是优化器的裁判，而统计信息是裁判的依据。由于使用了均匀分布和独立性等强假设，基数估算往往不准（通常倾向于低估）。这是数据库优化中最困难的部分。理解这些假设及其局限性，有助于理解为何数据库有时会选出“愚蠢”的计划。

教寄语*： 查询优化器是数据库中最迷人也最复杂的组件。复习时，请重点关注逻辑到物理的映射、Join 顺序的搜索空间以及基数估算的原理与缺陷。祝你学习顺利！